package com.jeff.practice;

import java.util.LinkedList;
import java.util.Queue;

public class NumIslandsBFS {
    public int numIslands(char[][] grid) {
        // 首先判断边界条件
        if (grid == null || grid.length == 0) {
            return 0;
        }
        // 定义遍历的行数和列数
        int rows = grid.length;
        int cols = grid[0].length;
        // 定义标记数组，用于记录是否访问过
        boolean[][] visited = new boolean[rows][cols];
        int islandCount = 0;
        //遍历元素
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                //判断当前位置是否为岛屿，并且未被访问过 满足这个条件才可以让大陆数量加一
                if (grid[r][c] == '1' && !visited[r][c]) {
                    bfs(grid, visited, r, c);
                    islandCount++;
                }
            }
        }

        return islandCount;
    }

    private void bfs(char[][] grid, boolean[][] visited, int r, int c) {
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{r, c});
        visited[r][c] = true;

        // 定义四个方向（上下左右）
        int[][] directions = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

        while (!queue.isEmpty()) {
            // 从队列中取出一个位置
            int[] position = queue.poll();
            // 遍历四个方向
            for (int[] direction : directions) {
                int newRow = position[0] + direction[0];
                int newCol = position[1] + direction[1];

                // 边界条件与标记数组判断是否可以访问 如果可以访问就入队
                if (newRow >= 0 && newRow < grid.length && newCol >= 0 && newCol < grid[0].length && grid[newRow][newCol] == '1' && !visited[newRow][newCol]) {
                    queue.offer(new int[]{newRow, newCol});
                    visited[newRow][newCol] = true;
                }
            }
        }
    }

    public static void main(String[] args) {
        NumIslandsBFS solution = new NumIslandsBFS();
        char[][] grid = {
                {'1', '1', '0', '0', '0'},
                {'1', '0', '0', '1', '1'},
                {'0', '0', '0', '0', '0'},
                {'0', '1', '1', '0', '0'},};
        System.out.println(solution.numIslands(grid)); // 输出: 3
    }
}
